\documentclass{ctexart}

\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{subfigure}
\usepackage{array}
\usepackage{float}

\title{微分方程数值解hw04 \\ Chapter9-Programming Assignments}


\author{陈冬勇 \\ 信息与计算科学 \ 3200103953}

\begin{document}

\maketitle

\section{编译说明}

\noindent
本次项目作业由\ \verb|Makefile|文件进行编译，以\ \verb|MultigridSolver.h|为头文件，输入\ \verb|make run|便能由\ \verb|main.cpp|产生可执行文件\ \verb|test|（一些数值、函数输入都已经存放在程序内部以及.json文件当中）并同时生成tex的.pdf文件，输入\ \verb|make clean|便能清理多余的文件，输入\ \verb|./test|便能运行可执行文件并得到结果并输出。实验报告中需要引用课本中定义、定理、引理、式子等会使用粗体字体进行表示。 [注：鉴于本人编程能力有限，因此本次项目作业只尝试去完成要求A以及附加要求a，即只对一维问题（dim=1）的相关要求进行了编程。]\\

\section{输入说明}
\noindent
可以通过修改\ \verb|hw04.json|的参数实现各种限制条件（输入）的更改得出不同的结果；同时后续如有需要，可以在\ \verb|main.cpp|中通过更改func为F1、F2、F3进行函数的切换，通过更改dim的值,统一使用\ \verb|int dim|作为模板参数输入，这样就可以将赋值传至包括头文件在内的各个子程序内，不需要再将其作为函数参数等进行输入，这样一来便可满足附加题中的要求a。 \\
以下介绍\ \verb|hw04.json|各参数的含义： \\
n:格点等分数，从[32,64,128,256]中取值； \\
Boundary\_condition:边界条件，分别由“DC”“NC”“MC”表示Dirichlet条件（以下简称D条件）、Neumann条件（以下简称N条件）、Mixed条件（以下简称M条件）； \\
Restriction\_operator:限制算子，分别由“FO”“IO”表示full-weighting限制算子（以下简称F限制算子）和injection限制算子（以下简称I限制算子）； \\
Interpolation\_operator:插值算子，分别由“Linear”“Quadratic”表示线性插值算子（以下简称L插值算子）和二次插值算子（以下简称Q插值算子）； \\
Grid\_type:网格类型，分别由“VC”“FMG”表示V-cycle网格（以下简称V网格）和FMG网格（以下简称F网格）； \\
Maximum\_iteration\_number:最大迭代次数； \\
Relative\_accuracy:相对精度，当解满足一定精度要求时停止迭代； \\
Initial\_guess:解的起始估计，直接选取零向量即可。 \\

\section{输出说明及数据结果分析}
\noindent
本次报告首先将展示一些特定限制条件下的程序运行结果，最后会对所有的情况用表格进行一个汇总，从而做到数据结果既有具体性，又有全面性，这也更有利于对数据进行进一步分析。
取定$dim=1, v_1=v_2=5, Relative\_accuracy=1 \cdot 10^{8}, Maximum\_iteration\_number=50.$以下首先对每种边界条件取一种限制条件（这里指挑选一种函数与算子的组合）给出V网格和F网格在n取不同值情况下的程序的具体输出，包括输出迭代次数、在同一行的残差第一范数和对应的残差缩减速率、误差无穷范数以及其关于n的收敛速率。 \\

\noindent
$1^{\circ}$\ Dirichlet条件：取定$F_1=e^{sin(x)}$,L插值算子和F限制算子。 \\
(1)V网格输出结果如下:
\begin{verbatim}
n = 32
Iteration number: 6
Residual's norm & Relative reduction rate: 
0.0667661
0.00196614 & 0.029
6.42177e-05 & 0.033
2.20744e-06 & 0.034
7.7647e-08 & 0.035
2.75175e-09 & 0.035
n = 64
Iteration number: 7
Residual's norm & Relative reduction rate: 
0.13639
0.0040692 & 0.03
0.00013323 & 0.033
4.55222e-06 & 0.034
1.59684e-07 & 0.035
5.67383e-09 & 0.036
2.03157e-10 & 0.036
n = 128
Iteration number: 7
Residual's norm & Relative reduction rate: 
0.275166
0.0082786 & 0.03
0.000273292 & 0.033
9.42666e-06 & 0.034
3.34352e-07 & 0.035
1.19836e-08 & 0.036
4.31472e-10 & 0.036
n = 256
Iteration number: 7
Residual's norm & Relative reduction rate: 
0.552706
0.0166925 & 0.03
0.000553543 & 0.033
1.91813e-05 & 0.035
6.83738e-07 & 0.036
2.46342e-08 & 0.036
8.9307e-10 & 0.036
Errornorm of each n: 
4.94148e-05, 1.23644e-05, 3.09089e-06, 7.72713e-07, 
Relative convergence rate(1og 2): 
1.99875, 2.0001, 2.00002, 
\end{verbatim}
根据数据结果，可以看出在Dirichlet边界条件下V网格仅需进行6到7次迭代，得到残差减小率固定在0.036左右；同时误差无穷范数的收敛阶趋向于2，这验证了程序的可执行性。 \\
(2)F网格输出结果如下：
\begin{verbatim}
n = 32
Iteration number: 3
Residual's norm & Relative reduction rate: 
2.14536e-05
4.98883e-08 & 0.002
1.18816e-10 & 0.002
n = 64
Iteration number: 3
Residual's norm & Relative reduction rate: 
6.04714e-05
1.39819e-07 & 0.002
3.30252e-10 & 0.002
n = 128
Iteration number: 3
Residual's norm & Relative reduction rate: 
0.000171022
3.95432e-07 & 0.002
9.34012e-10 & 0.002
n = 256
Iteration number: 3
Residual's norm & Relative reduction rate: 
0.00048371
1.11842e-06 & 0.002
2.64172e-09 & 0.002
Errornorm of each n: 
4.94147e-05, 1.23644e-05, 3.09088e-06, 7.72706e-07, 
Relative convergence rate(1og 2): 
1.99875, 2.0001, 2.00003, 
\end{verbatim}
根据数据结果，可以看出在Dirichlet边界条件下F网格仅需进行3次迭代，得到残差减小率固定在0.002左右；同时误差无穷范数的收敛阶趋向于2，这验证了程序的可执行性。 \\

\noindent
$2^{\circ}$\ Neumann条件:取定$F_2=-e^{-x}$,Q插值算子和F限制算子。 \\
(1)V网格输出如下：
\begin{verbatim}
n = 32
Iteration number: 18
Residual's norm & Relative reduction rate: 
0.683687
0.214878 & 0.314
0.0736774 & 0.343
0.02676 & 0.363
0.0100642 & 0.376
0.00386179 & 0.384
0.00149846 & 0.388
0.000584978 & 0.39
0.000229115 & 0.392
8.98928e-05 & 0.392
3.53021e-05 & 0.393
1.38705e-05 & 0.393
5.45127e-06 & 0.393
2.14271e-06 & 0.393
8.4229e-07 & 0.393
3.31114e-07 & 0.393
1.30167e-07 & 0.393
5.11718e-08 & 0.393
n = 64
Iteration number: 20
Residual's norm & Relative reduction rate: 
1.59711
0.525459 & 0.329
0.188053 & 0.358
0.0710305 & 0.378
0.0277819 & 0.391
0.0111068 & 0.4
0.00450009 & 0.405
0.00183791 & 0.408
0.00075419 & 0.41
0.000310343 & 0.411
0.000127911 & 0.412
5.27694e-05 & 0.413
2.17819e-05 & 0.413
8.9939e-06 & 0.413
3.71434e-06 & 0.413
1.53413e-06 & 0.413
6.33677e-07 & 0.413
2.61753e-07 & 0.413
1.08124e-07 & 0.413
4.46643e-08 & 0.413
n = 128
Iteration number: 21
Residual's norm & Relative reduction rate: 
3.48145
1.18387 & 0.34
0.436916 & 0.369
0.169867 & 0.389
0.068387 & 0.403
0.028176 & 0.412
0.0117843 & 0.418
0.00497622 & 0.422
0.00211413 & 0.425
0.000901606 & 0.426
0.000385422 & 0.427
0.000165006 & 0.428
7.07067e-05 & 0.429
3.03159e-05 & 0.429
1.30027e-05 & 0.429
5.57818e-06 & 0.429
2.39337e-06 & 0.429
1.02699e-06 & 0.429
4.40699e-07 & 0.429
1.89118e-07 & 0.429
8.11582e-08 & 0.429
n = 256
Iteration number: 23
Residual's norm & Relative reduction rate: 
7.30364
2.54115 & 0.348
0.957562 & 0.377
0.379998 & 0.397
0.156199 & 0.411
0.0657783 & 0.421
0.0281601 & 0.428
0.0121897 & 0.433
0.00531621 & 0.436
0.00233013 & 0.438
0.00102451 & 0.44
0.000451385 & 0.441
0.000199141 & 0.441
8.79333e-05 & 0.442
3.88504e-05 & 0.442
1.71711e-05 & 0.442
7.59117e-06 & 0.442
3.3565e-06 & 0.442
1.48426e-06 & 0.442
6.5639e-07 & 0.442
2.90291e-07 & 0.442
1.28386e-07 & 0.442
5.67817e-08 & 0.442
Errornorm of each n: 
0.000104189, 2.53191e-05, 6.24839e-06, 1.55422e-06, 
Relative convergence rate(1og 2): 
2.0409, 2.01867, 2.0073, 
\end{verbatim}
根据数据结果，可以看出在Neumann边界条件下V网格需进行18到23次迭代，随n的增大迭代次数增多，得到残差减小率在0.393到0.442，随n的增大收敛速度变慢；同时误差无穷范数的收敛阶趋向于2，这验证了程序的可执行性。 \\
(2)F网格输出结果如下：
\begin{verbatim}
n = 32
Iteration number: 6
Residual's norm & Relative reduction rate: 
0.0304781
0.0020766 & 0.068
0.000139085 & 0.067
9.27667e-06 & 0.067
6.18938e-07 & 0.067
4.1359e-08 & 0.067
n = 64
Iteration number: 6
Residual's norm & Relative reduction rate: 
0.0924511
0.00622105 & 0.067
0.000408079 & 0.066
2.65011e-05 & 0.065
1.71484e-06 & 0.065
1.10854e-07 & 0.065
n = 128
Iteration number: 7
Residual's norm & Relative reduction rate: 
0.273243
0.0183699 & 0.067
0.00119845 & 0.065
7.71524e-05 & 0.064
4.93789e-06 & 0.064
3.15244e-07 & 0.064
2.01052e-08 & 0.064
n = 256
Iteration number: 7
Residual's norm & Relative reduction rate: 
0.793332
0.05344 & 0.067
0.00348477 & 0.065
0.000223847 & 0.064
1.42783e-05 & 0.064
9.07767e-07 & 0.064
5.76247e-08 & 0.063
Errornorm of each n: 
0.000104176, 2.53119e-05, 6.23446e-06, 1.54712e-06, 
Relative convergence rate(1og 2): 
2.04113, 2.02148, 2.01068, 
\end{verbatim}
根据数据结果，可以看出在Neumann边界条件下F网格需进行6到7次迭代，得到残差减小率在0.065左右，相比较远好于V网格；同时误差无穷范数的收敛阶趋向于2，这验证了程序的可执行性。 \\

\noindent
$3^{\circ}$\ Mixed条件:取定$F_3=cos(x)+1$,Q插值算子和I限制算子。 \\
(1)V网格输出如下：
\begin{verbatim}
n = 32
Iteration number: 13
Residual's norm & Relative reduction rate: 
0.0233879
0.00504529 & 0.216
0.0014732 & 0.292
0.000395639 & 0.269
0.000102846 & 0.26
2.65515e-05 & 0.258
6.8419e-06 & 0.258
1.76222e-06 & 0.258
4.53828e-07 & 0.258
1.16872e-07 & 0.258
3.00969e-08 & 0.258
7.7506e-09 & 0.258
1.99607e-09 & 0.258
n = 64
Iteration number: 14
Residual's norm & Relative reduction rate: 
0.0587185
0.0148291 & 0.253
0.00434193 & 0.293
0.00119523 & 0.275
0.000318979 & 0.267
8.43977e-05 & 0.265
2.22656e-05 & 0.264
5.86856e-06 & 0.264
1.5463e-06 & 0.263
4.07391e-07 & 0.263
1.07328e-07 & 0.263
2.82754e-08 & 0.263
7.4492e-09 & 0.263
1.96269e-09 & 0.263
n = 128
Iteration number: 14
Residual's norm & Relative reduction rate: 
0.111578
0.0265827 & 0.238
0.00800784 & 0.301
0.00227197 & 0.284
0.000622381 & 0.274
0.000168465 & 0.271
4.53849e-05 & 0.269
1.22047e-05 & 0.269
3.27976e-06 & 0.269
8.81121e-07 & 0.269
2.36691e-07 & 0.269
6.35786e-08 & 0.269
1.70784e-08 & 0.269
4.58607e-09 & 0.269
n = 256
Iteration number: 15
Residual's norm & Relative reduction rate: 
0.193905
0.0406747 & 0.21
0.012577 & 0.309
0.00367035 & 0.292
0.00103126 & 0.281
0.000285169 & 0.277
7.83019e-05 & 0.275
2.14347e-05 & 0.274
5.85975e-06 & 0.273
1.60097e-06 & 0.273
4.37296e-07 & 0.273
1.19435e-07 & 0.273
3.26183e-08 & 0.273
8.90835e-09 & 0.273
2.43322e-09 & 0.273
Errornorm of each n: 
0.000300795, 7.57283e-05, 1.90007e-05, 4.75932e-06, 
Relative convergence rate(1og 2): 
1.98988, 1.99478, 1.99723, 
\end{verbatim}
根据数据结果，可以看出在Mixed边界条件下V网格需进行13到15次迭代，得到残差减小率在0.258到0.273；同时误差无穷范数的收敛阶趋向于2，这验证了程序的可执行性。 \\
(2)F网格输出结果如下：
\begin{verbatim}
n = 32
Iteration number: 5
Residual's norm & Relative reduction rate: 
0.000750616
3.15669e-05 & 0.042
1.32594e-06 & 0.042
5.56975e-08 & 0.042
2.33963e-09 & 0.042
n = 64
Iteration number: 5
Residual's norm & Relative reduction rate: 
0.00120857
4.97376e-05 & 0.041
2.0459e-06 & 0.041
8.41556e-08 & 0.041
3.46165e-09 & 0.041
n = 128
Iteration number: 5
Residual's norm & Relative reduction rate: 
0.00180717
7.35609e-05 & 0.041
2.99381e-06 & 0.041
1.21842e-07 & 0.041
4.95876e-09 & 0.041
n = 256
Iteration number: 5
Residual's norm & Relative reduction rate: 
0.00262179
0.00010603 & 0.04
4.28795e-06 & 0.04
1.73407e-07 & 0.04
7.0127e-09 & 0.04
Errornorm of each n: 
0.000300795, 7.57285e-05, 1.89992e-05, 4.76001e-06, 
Relative convergence rate(1og 2): 
1.98987, 1.9949, 1.9969, 
\end{verbatim}
根据数据结果，可以看出在Mixed边界条件下F网格需进行5次迭代，得到残差减小率在0.041左右，相比较好于V网格；同时误差无穷范数的收敛阶趋向于2，这验证了程序的可执行性。 \\

\section{相对精度、残差缩减率、收敛阶测试分析}
\noindent
根据题意，我们需要将$\epsilon$从$1 \cdot 10^{-8}$减小到$2.2 \cdot 10^{-16}$,以D条件下的V网格为例绘制不同$\epsilon$取值下的迭代次数的表格如下：（做了很多数值调试，以下表格将仅呈现一部分） \\
\begin{table}[H]
\renewcommand{\arraystretch}{1.2}
 \centering
 \setlength{\tabcolsep}{0.3cm}{
\begin{tabular}{c|cccc}
     $\epsilon$ & n=32 & n=64 & n=128 & n=256 \\
     $1 \cdot 10^{-8}$ & 6 & 7 & 7 & 7 \\
     $1 \cdot 10^{-10}$ & 8 & 8 & 8 & 9 \\
     $3 \cdot 10^{-11}$ & 8 & 8 & 9 & 9 \\
     $2 \cdot 10^{-11}$ & 8 & 8 & 9 & 49 \\
     $1 \cdot 0^{-11}$ & 8 & 9 & 9 & 49 \\
     $6 \cdot 10^{-12}$ & 8 & 9 & 11 & 49 \\
     $5 \cdot 10^{-12}$ & 9 & 9 & 49 & 49 \\
     $2 \cdot 10^{-12}$ & 9 & 9 & 49 & 49 \\
     $1 \cdot 10^{-12}$ & 9 & 49 & 49 & 49 \\
     $3 \cdot 10^{-13}$ & 11 & 49 & 49 & 49 \\
     $2 \cdot 10^{-13}$ & 49 & 49 & 49 & 49 \\
     $2.2 \cdot 10^{-16}$ & 49 & 49 & 49 & 49 \\
\end{tabular}}
\end{table}
\noindent
我们通过该简易表格进行分析，随着$\epsilon$的不断降低，n越大则越早无法在50次迭代内达到对应的精度，我们给出临界点的一个大致判断：n=32时，$\epsilon_0=2 \cdot 10^{-13}$;n=64时，$\epsilon_0=1 \cdot 10^{-12}$;n=128时，$\epsilon_0=5 \cdot 10^{-12}$;n=256时，$\epsilon_0=2 \cdot 10^{-11}$;以上给出了我们需要的critical value.首先发现无法在$\epsilon$小于等于$\epsilon_0$时无法在50次迭代内满足精度要求的原因在于方程在进一步迭代时残差的缩减率接近于1；而对于F网格进行类似的调试时即使$\epsilon$取最小值在n取各值时只需要6次迭代就能满足精度要求；最终我们得到的结论如下：程序在特定情况下无法满足精度要求的原因是整个模型的固有误差，这包括Jacobi迭代的精度限制、插值算子和线性算子作用时产生的误差等，这导致利用多重网格虽然能够加快Jacobi迭代的收敛速度，但是也可能会造成程序在相对精度降低到一定程度时无法收敛，是有利有弊的。\\
以下将综合诸多数据全面分析残差缩减率、误差无穷范数收敛阶： \\
\begin{table}[H]
\renewcommand{\arraystretch}{1.2}
 \centering
 \setlength{\tabcolsep}{0.15cm}{
\begin{tabular}{c|cccccccc}
     Boundary \& n,Grid type & 32,V & 32,F & 64,V & 64,F & 128,V & 128,F & 256,V & 256,F \\
     D-condition & 0.035 & 0.002 & 0.036 & 0.002 & 0.036 & 0.002 & 0.036 & 0.002 \\
     N-condition & 0.393 & 0.067 & 0.413 & 0.065 & 0.429 & 0.064 & 0.442 & 0.062 \\
     M-condition & 0.258 & 0.042 & 0.263 & 0.041 & 0.269 & 0.041 & 0.273 & 0.040 \\
\end{tabular}}
\end{table}
\noindent
我们通过简易表格进行分析（数值为残差缩减率，即reduction rate），发现：在网格类型上F网格的收敛效果比V网格更好；在边界条件类型上D条件的收敛效果最好，N条件的收敛效果最差，M条件介于两者之间；在n的四种数值下对F网格的残差缩减率影响很小，对V网格的残差缩减率速率影响较大，n越大残差缩减率越大，收敛速率变慢。 \\
\begin{table}[H]
\renewcommand{\arraystretch}{1.2}
 \centering
 \setlength{\tabcolsep}{0.3cm}{
\begin{tabular}{c|cc}
     Boundary \& Grid type &  V-cycle & FMG \\
     D-condition & 2.0001 & 2.0001 \\
     N-condition & 2.0187 & 2.0215 \\
     M-condition & 1.9948 & 1.9949 \\
\end{tabular}}
\end{table}
\noindent
我们通过简易表格进行分析（数值为误差无穷范数关于n的平均收敛速率，以2为底取对数，即covergence rate），发现：在网格类型上两种网格的收敛阶几乎一致；在边界条件类型上F网格的收敛效果比V网格更好；在边界条件类型上D条件的收敛效果最好，N条件的收敛效果最差，M条件介于两者之间；并且总的来说收敛阶都趋向于2，这与我们的认知是相符的。 \\

\end{document}
